Search results for "design [accelerator]"
showing 10 items of 594 documents
Biased Modern Heuristics for the OCST Problem
2011
Biasing modern heuristics is an appropriate possibility in designing problem-specific and high-quality modern heuristics. If we have knowledge about a problem we can bias the design elements of modern heuristics, namely the representation and search operator, fitness function, the initial solution, or even the search strategy. This chapter presents a case study on how the performance of modern heuristics can be increased by biasing the design elements towards high-quality solutions. Results show that problem-specific and biased modern heuristics outperform standard variants and even for large problem instances high-quality solutions can be found.
An efficient variable neighborhood search heuristic for very large scale vehicle routing problems
2007
In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are use…
GRASP for the uncapacitated r-allocation p-hub median problem
2014
In this paper we propose a heuristic for the Uncapacitated r-Allocation p-Hub Median Problem. In the classical p-hub location problem, given a set of nodes with pairwise traffic demands, we must select p of them as hub locations and route all traffics through them at a minimum cost. We target here an extension, called the r-allocation p-hub median problem, recently proposed by Yaman [19], in which every node is assigned to r of the p selected hubs (r@?p) and we are restricted to route the traffic of the nodes through their associated r hubs. As it is usual in this type of problems, our method has three phases: location, assignment and routing. Specifically, we propose a heuristic based on t…
Active-guided evolution strategies for large-scale capacitated vehicle routing problems
2007
We present an adaptation of the active-guided evolution strategies metaheuristic for the capacitated vehicle routing problem. The capacitated vehicle routing problem is a classical problem in operations research in which a set of minimum total cost routes must be determined for a fleet of identical capacitated vehicles in order to service a number of demand or supply points. The applied metaheuristic combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. The computational experiments were carried out on a set of 76 benchmark problems. The results demonstrate that the suggested method is highly competitive, …
Most Diverse Near-Shortest Paths
2021
Computing the shortest path in a road network is a fundamental problem that has attracted lots of attention. However, in many real-world scenarios, determining solely the shortest path is not enough as users want to have additional, alternative ways of reaching their destination. In this paper, we investigate a novel variant of alternative routing, termed the k-Most Diverse Near-Shortest Paths (kMDNSP). In contrast to previous work, kMDNSP aims at maximizing the diversity of the recommended paths, while bounding their length based on a user-defined constraint. Our theoretical analysis proves the NP-hardness of the problem at hand. To compute an exact solution to kMDNSP, we present an algori…
Optimal Delay-Power Tradeoff in Sparse Delay Tolerant Networks: a preliminary study
2006
In this paper we present a first attempt to study analytically the tradeoff between delivery delay and resource consumption for epidemic routing in Delay Tolerant Networks. We assume that the nodes cooperate in order to minimize a common cost equal to a weighted sum of the packet delivery delay and the total number of copies, which is strongly related to the power consumption. In this framework we determine the best policy each node should deploy in a very simple scenario where all the nodes have perfect knowledge of the system status. The result is used as an ideal reference to evaluate the performance of some heuristics proposed, investigating potential performance improvements and config…
On the Distance-Constrained Close Enough Arc Routing Problem
2021
[EN] Arc routing problems consist basically of finding one or several routes traversing a given set of arcs and/or edges that must be serviced. The Close-Enough Arc Routing Problem, or Generalized Directed Rural Postman Problem, does not assume that customers are located at specific arcs, but can be serviced by traversing any arc of a given subset. Real-life applications include routing for meter reading, in which a vehicle equipped with a receiver travels a street network. If the vehicle gets within a certain distance of a meter, the receiver collects its data. Therefore, only a few streets which are close enough to the meters need to be traversed. In this paper we study the generalization…
Lower bounds and heuristics for the Windy Rural Postman Problem
2020
[EN] In this paper we present several heuristic algorithms and a cutting-plane algorithm for the Windy Rural Postman Problem. This problem contains several important Arc Routing Problems as special cases and has very interesting real-life applications. Extensive computational experiments over different sets of instances are also presented.
Two-phase branch-and-cut for the mixed capacitated general routing problem
2015
The Mixed Capacitated General Routing Problem (MCGRP) is defined over a mixed graph, for which some vertices must be visited and some links must be traversed at least once. The problem consists of determining a set of least-cost vehicle routes that satisfy this requirement and respect the vehicle capacity. Few papers have been devoted to the MCGRP, in spite of interesting real-world applications, prevalent in school bus routing, mail delivery, and waste collection. This paper presents a new mathematical model for the MCGRP based on two-index variables. The approach proposed for the solution is a two-phase branch-and-cut algorithm, which uses an aggregate formulation to develop an effective …
Optimization under Uncertainty and Linear Semi-Infinite Programming: A Survey
2001
This paper deals with the relationship between semi-infinite linear programming and decision making under uncertainty in imprecise environments. Actually, we have reviewed several set-inclusive constrained models and some fuzzy programming problems in order to see if they can be solved by means of a linear semi-infinite program. Finally, we present some numerical examples obtained by using a primal semi-infinite programming method.